package leetcode.templates.suffixarray;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int[] rk;
	int len, k;

	public int sa(String str) {
		len = str.length();
		Integer[] sa = new Integer[len];
		rk = new int[len];
		for (int i = 0; i < len; i++) {
			sa[i] = i;
			rk[i] = str.charAt(i) - 'a';
		}
		int[] rk2 = new int[len];
		for (k = 1; k < len; k <<= 1) {
			Arrays.sort(sa, (a, b) -> cmp(a, b));//
			rk2[sa[0]] = 0;
			for (int i = 1; i < len; i++) {
				rk2[sa[i]] = rk2[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) < 0 ? 1 : 0);
			}
			rk = Arrays.copyOf(rk2, len);
		}
		this.debug(str, sa);
		return sa[len - 1];
	}

	private int cmp(int l, int r) {
		if (rk[l] != rk[r]) {
			return rk[l] - rk[r];
		}
		int L = l + k < len ? rk[l + k] : -1;
		int R = r + k < len ? rk[r + k] : -1;
		return L - R;
	}

	private void debug(String str, Integer[] sa) {
		for (int i = 0; i < len; i++) {
			System.out.println(str.substring(sa[i]));
		}
		H.print(sa);
		H.print(rk);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		System.out.println("abccbac");
		System.out.println("后缀数组");
		this.sa("abccbac");
		System.out.println("azbazbzaz");
		System.out.println("后缀数组");
		this.sa("azbazbzaz");
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
